import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/11 9:24
 * @description 动态规划，dp[i]为将正整数i拆分为至少两个正整数的和之后，这些正整数的最大乘积
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.integerBreak(20);
    }

    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        // dp[0] 和 dp[1] == 0；
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                // i 拆分为 j 和 i-j ，那么i-j可以选择不拆，或者继续拆
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}